//
//  main.c
//  MaxSum-求最大字段和
//
//  Created by zhuoooo on 2022/6/22.
//  Copyright © 2022年 zhuoooo. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100

int max_Sum1(int num[],int n);//蛮力法求解最大字段和
int max_Sum2(int num[], int left, int right);//分治法求解最大字段和
int max_Sum3(int num[], int len);//动态规划求解最大字段和

int main(int argc, const char * argv[]) {
    
    while(1){
        int num[N], length, i;
        printf("请输入数字的个数：");
        scanf("%d", &length);
        printf("请输入数字元素值：\n");
        for(i = 0; i < length; i++)//随机生成length个数
        {
            num[i] = rand()%75-35;
        }
    
        printf("生成的随机数字为：\n");
        for(i = 0; i < length; i++)
        {
            printf("%4d", num[i]);
        }
        printf("\n");
        
        int res = 0;
        int number;
        printf("1.最大字段和为（蛮力法）\n2.最大字段和为（分治法）\n3.最大字段和为（动态规划）\n0.退出\n");
        printf("请输入您要选择的选项：");
        scanf("%d", &number);
        
        if (number == 1) {
            res = max_Sum1(num, length-1);
            printf("最大字段和为（蛮力法）：%d\n", res);
        }else if (number == 2){
            res = max_Sum3(num, length);
            printf("最大字段和为（分治法）：%d\n", res);
        }else if (number == 3){
            res = max_Sum2(num, 0, length-1);
            printf("最大字段和为（动态规划）：%d\n", res);
        }
        else if (number == 0){
            break;
        }else{
            printf("输入错误，请重新输入!\n“");
            continue;
        }
        
    }
    return 0;
}

int max_Sum1(int num[],int n)
{
    int i, j, maxn=0;
    for(i = 0; i <= n; i++)
    {
        int trmp = 0;
        for(j = i; j <= n; j++)//循环的次数减少
        {
            
            trmp += num[j];
            if(trmp > maxn)//如果前几项有大于之前的最大字段和就修改
            {
                maxn = trmp;
            }
        }
    }
    return maxn;
}

int max_Sum2(int num[], int left, int right)
{
    int sum = 0, midSum = 0, leftSum = 0, rightSum = 0;
    int i, j, center, s1, s2, lefts, rights;
    if(left == right)//如果长度为1，直接求解
    {
        sum = num[left];
    }
    else
    {
        center = (left + right) / 2;    //划分
        leftSum = max_Sum2(num, left, center);//对于情况1，递归求解
        rightSum = max_Sum2(num, center+1, right);//对于情况2，递归求解
        s1 = 0;                         // 对于情况3，先求解s1
        lefts = 0;
        for(i = center; i >= left; i--)
        {
            lefts += num[i];
            if(lefts > s1)
            {
                s1 = lefts;
            }
        }
        s2 = 0;                         //在求解S2
        rights = 0;
        for(j = center+1; j <= right; j++)
        {
            rights += num[j];
            if(rights > s2)
            {
                s2 = rights;
            }
        }
        
        midSum = s1 + s2;       //计算情况3的最大字段和
        if(midSum < leftSum)    //合并解，取最大值
        {
            sum = leftSum;
        }else{
            sum = midSum;
        }
        if(sum < rightSum){
            sum = rightSum;
        }else{
            sum = midSum;
        }
        
    }
    return sum;
}

int max_Sum3(int num[], int len)
{
    int max = 0, tmp[N], i, j;
    tmp[0] = num[0];
    max = tmp[0];
    for(j = 0; j < len; j++)//找到字段中的正数
    {
        if(num[j] < 0){
            continue;
        }else{
            break;
        }
    }
    if(j != len){       //公式tmp[i] = tmp[i-1] + num[i]
        for(i = 1; i < len; i++)
        {
            if(tmp[i-1] >= 0)//如果前面几个数大于0，就加上，反之，不加
                tmp[i] = tmp[i-1] + num[i];
            else
                tmp[i] = num[i];
            if(tmp[i] >= max)
            {
                max = tmp[i];
            }
        }
    }else{
        max = 0;
    }
    
    return max;
}
